package com.note.feng.leetcode.algorithms.easy.six;

import java.util.HashMap;
import java.util.Map;

public class SixHundredNinetySeven {
    /**
     * 697 数组的度
     * 给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。
     *
     * 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
     *
     * 示例 1：
     *
     * 输入：nums = [1,2,2,3,1]
     * 输出：2
     * 解释：
     * 输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
     * 连续子数组里面拥有相同度的有如下所示：
     * [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
     * 最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。
     * 示例 2：
     *
     * 输入：nums = [1,2,2,3,1,4,2]
     * 输出：6
     * 解释：
     * 数组的度是 3 ，因为元素 2 重复出现 3 次。
     * 所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。
     *
     * 提示：
     *
     * nums.length 在 1 到 50,000 范围内。
     * nums[i] 是一个在 0 到 49,999 范围内的整数。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/degree-of-an-array
     */
    /**
     * 解法：哈希
     * 遍历数组，每个元素出现的次数、第一次出现的小标、最后一次出现的下标，都用 map 存下来，
     * key 是元素值，value 是一个数组，第一个是元素出现的次数，第二个是元素第一次出现的下标，第二个是元素最后一次出现的下标
     * 最后遍历 map ，若只有一个元素出现的次数最多，直接返回这个元素两个下标的差；
     * 若有多个元素出现的次数一样，且是最多的，返回下标差最小的那个。
     * @param nums
     * @return
     */
    public int findShortestSubArray(int[] nums) {
        Map<Integer, int []> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])){
                map.get(nums[i])[0]++;
                map.get(nums[i])[2] = i;
            }else{
                map.put(nums[i], new int[]{1, i, i});
            }
        }
        int max = 0,minLen = 0;
        for (Integer integer : map.keySet()){
            int [] arr = map.get(integer);
            if(max < arr[0]){
                max = arr[0];
                minLen = arr[2] - arr[1] + 1;
            }else if(max == arr[0]){
                minLen = Math.min(minLen, arr[2] - arr[1] + 1);
            }
        }
        return minLen;
    }
}
